package ali;


public class Solution_21 {

	private  int max; //最大直径

	public int diameterOfBinaryTree(TreeNode root) {
		max = 1;
		depth(root);
		return max - 1;
	}

	private int depth(TreeNode node) {

		if (node == null) {
			return 0;// 访问到空节点了，返回0
		}

		int l = depth(node.left);// 左儿子为根的子树的深度
		int r = depth(node.right);// 右儿子为根的子树的深度
		max = Math.max(max, l + r + 1);// 计算直径，即L+R+1 并更新最大直径
		return Math.max(l, r) + 1; // 返回该节点为根的子树的深度
	}

	public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

}